1. Technical Field
The present invention relates generally to data storage and retrieval and, more particularly to systems and methods for improving data storage and retrieval bandwidth utilizing lossless and/or lossy data compression and decompression.
2. Description of the Related Art
Information may be represented in a variety of manners. Discrete information such as text and numbers are easily represented in digital data. This type of data representation is known as symbolic digital data. Symbolic digital data is thus an absolute representation of data such as a letter, figure, character, mark, machine code, or drawing.
Continuous information such as speech, music, audio, images and video frequently exists in the natural world as analog information. As is well-known to those skilled in the art, recent advances in very large scale integration (VLSI) digital computer technology have enabled both discrete and analog information to be represented with digital data. Continuous information represented as digital data is often referred to as diffuse data. Diffuse digital data is thus a representation of data that is of low information density and is typically not easily recognizable to humans in its native form.
There are many advantages associated with digital data representation. For instance, digital data is more readily processed, stored, and transmitted due to its inherently high noise immunity. In addition, the inclusion of redundancy in digital data representation enables error detection and/or correction. Error detection and/or correction capabilities are dependent upon the amount and type of data redundancy, available error detection and correction processing, and extent of data corruption.
One outcome of digital data representation is the continuing need for increased capacity in data processing, storage, and transmittal. This is especially true for diffuse data where increases in fidelity and resolution create exponentially greater quantities of data. Data compression is widely used to reduce the amount of data required to process, transmit, or store a given quantity of information. In general, there are two types of data compression techniques that may be utilized either separately or jointly to encode/decode data: lossy and lossless data compression.
Lossy data compression techniques provide for an inexact representation of the original uncompressed data such that the decoded (or reconstructed) data differs from the original unencoded/uncompressed data. Lossy data compression is also known as irreversible or noisy compression. Negentropy is defined as the quantity of information in a given set of data. Thus, one obvious advantage of lossy data compression is that the compression ratios can be larger than that dictated by the negentropy limit, all at the expense of information content. Many lossy data compression techniques seek to exploit various traits within the human senses to eliminate otherwise imperceptible data. For example, lossy data compression of visual imagery might seek to delete information content in excess of the display resolution or contrast ratio of the target display device.
On the other hand, lossless data compression techniques provide an exact representation of the original uncompressed data. Simply stated, the decoded (or reconstructed) data is identical to the original unencoded/uncompressed data. Lossless data compression is also known as reversible or noiseless compression. Thus, lossless data compression has, as its current limit, a minimum representation defined by the negentropy of a given data set.
It is well known within the current art that data compression provides several unique benefits. First, data compression can reduce the time to transmit data by more efficiently utilizing low bandwidth data links. Second, data compression economizes on data storage and allows more information to be stored for a fixed memory size by representing information more efficiently.
One problem with the current art is that the bandwidth and storage capacity of existing memory storage devices severely limit the performance of consumer, entertainment, office, workstation, servers, and mainframe computers for all disk and memory intensive operations. For example, magnetic disk mass storage devices currently employed in a variety of home, business, and scientific computing applications suffer from significant seek-time access delays along with profound read/write data rate limitations. Currently the fastest available (10,000) rpm disk drives support only a 22 Megabyte per second data rate (MB/sec). This is in stark contrast to the modern Personal Computer""s Peripheral Component Interconnect (PCI) Bus""s input/output capability of 528 MB/sec and internal local bus capability of over 1,064 MB/sec. Substantially faster processor, internal local bus memory, and I/O bus bandwidths are expected in the near future.
Another problem within the current art is that emergent high performance disk interface standards such as the Small Computer Systems Interface (SCSI-3) and Fibre Channel offer only the promise of higher data transfer rates through intermediate data buffering in random access memory. These interconnect strategies do not address the fundamental problem that all modern magnetic disk storage devices for the personal computer marketplace are still limited by the same physical media restriction of 22 MB/sec. Faster disk access data rates are only achieved by the high cost solution of simultaneously accessing multiple disk drives with a technique known within the art as data striping.
Additional problems with bandwidth limitations similarly occur within the art by all other forms of sequential, pseudo-random, and random access mass storage devices. Typically mass storage devices include magnetic and optical tape, magnetic and optical disks, and various solid-state mass storage devices. It should be noted that the present invention applies to all forms and manners of memory devices including storage devices utilizing magnetic, optical, and chemical techniques, or any combination thereof.
The present invention is directed to systems and methods for providing accelerated data storage and retrieval by utilizing lossless and lossy data compression and decompression. The present invention provides an effective increase of the data storage and retrieval bandwidth of a memory storage device. In one aspect of the present invention, a method for providing accelerated data storage comprises the steps of receiving a digital data stream at an input data transmission rate which is greater than a data storage rate of a target storage device, compressing the digital data stream at a compression rate that increases the effective data storage rate of the target storage device, and storing the compressed digital data stream in the target storage device. The step of compressing may be performed using lossless data compression, lossy data compression or a combination of lossless and lossy data compression.
In another aspect of the present invention, the compression process comprises the steps of reading a first parameter that is indicative of a compression type to be applied to the input digital data stream, and selecting at least one allowable encoder based on the first parameter.
In yet another aspect, the compression process further comprises the step of reading a second parameter that is indicative of an amount of information loss that is permissible, if lossy data compression is selected.
In another aspect of the present invention, a method for providing accelerated retrieval of stored data comprises the steps of retrieving a compressed digital data stream from a target storage device at a rate equal to a data access rate of the target storage device and decompressing the compressed data at a decompression rate that increases the effective data access rate of the target storage device. The step of compressing may be performed using lossless data compression, lossy data compression or a combination of lossless and lossy data compression.
In yet another aspect of the present invention, the decompression process comprises the steps of reading a first parameter that is indicative of a decompression type to be applied to the compressed digital data stream, and selecting at least one allowable decoder based on the first parameter.
In another aspect, the decompression process further comprises the step of reading a second parameter that is indicative of an amount of information loss that is permissible, if lossy data decompression is selected.
In yet another aspect of the present invention, the method for providing accelerated data storage utilizes a compression ratio that is at least equal to the ratio of the input data transmission rate to the data storage rate so as to provide continuous storage of the input data stream at the input data transmission rate. Moreover, the method for providing accelerated data retrieval utilizes a decompression ratio which is equal to or greater than the ratio of the data access rate to a maximum accepted output data transmission rate so as to provide a continuous and optimal data output transmission rate.
In another aspect of the present invention, data storage and retrieval acceleration is employed in a disk storage adapter to reduce the time required to store and retrieve data from computer to a disk memory device.
In another aspect of the present invention, data storage and retrieval acceleration is employed in conjunction with random access memory to reduce the time required to store and retrieve data from random access memory.
In another aspect of the present invention, data storage and retrieval acceleration is employed in a video data storage system to reduce the time required to store digital video data.
In another aspect of the present invention, data storage and retrieval acceleration is employed in a display controller to reduce the time required to send display data to the display controller or processor.
In another aspect of the present invention, data storage and retrieval acceleration is employed in an input/output controller to reduce the time required to store, retrieve, or transmit data various forms of data.
The present invention is realized due to recent improvements in processing speed, inclusive of dedicated analog and digital hardware circuits, central processing units, digital signal processors, dedicated finite state machines (and any hybrid combinations thereof), that, coupled with advanced data compression and decompression algorithms, are enabling of ultra high bandwidth data compression and decompression methods that enable improved data storage and retrieval bandwidth.